Date: Thu, 21 Nov 1996 20:14:39 GMT
Server: Apache/1.1.1
Content-type: text/html
Set-Cookie: Apache=gs359833848607279582; path=/
Content-length: 2248
Last-modified: Mon, 27 Mar 1995 17:25:09 GMT

<HTML>
<HEAD><title>Research Interests:  Laszlo Babai</title></HEAD>

<BODY>

<h1>Laszlo Babai</h1>
<hr>
	My fields of interest include computational complexity theory,
algorithms, combinatorics, and finite groups.  Randomization plays a role
in each area.<p>
	A major recent result, obtained in collaboration with Lance Fortnow,
our former graduate students Carsten Lund (Ph.D. '91) and Mario Szegedy
(Ph.D. '89), and Leonid Levin of Boston University, is the invention of
"transparent proofs," proofs one can verify by a small number of spotchecks.
We have shown that all formal mathematical proofs can be transformed into
transparent form.  The result and its subsequent refinements have found
applications in areas as seemingly remote as approximate discrete optimization
(e.g., nearly optimal traveling salesman routing).<P>
	In joint work with graduate student Bob Beals (Ph.D. '93), we have
found Monte Carlo algorithms with guaranteed performance bounds to find
structural elements of matrix groups (given by a list of generators).  The
work involves methods from group theory, combinatorics, and probability
theory (Markov chains).<P>
	I have been studying group actions on graphs.  A recent result
provides an asymptotic classification of finite vertex-symmetric graphs
with an excluded minor, using connections to hyperbolic geometry.<P>

<hr>
<!WA0><a href="http://cs-www.uchicago.edu/info/admin/html/faculty-research.html">
<!WA1><img align=middle src="http://cs-www.uchicago.edu/images/directional/back32x32.gif" border=0 ALT="Faculty Interests"> Back to faculty interests home page.</a>

<!WA2><a href="http://cs-www.uchicago.edu/">
<!WA3><img align=middle
src="http://cs-www.uchicago.edu/images/buttons/text/cshome-button.gif" border=0 ALT="Home"></a>

<!WA4><a href="http://cs-www.uchicago.edu/info/admin/html/people.html">
<!WA5><img align=middle
src="http://cs-www.uchicago.edu/images/buttons/text/people-button.gif" border=0 ALT="People"></a>

<!WA6><a href="http://cs-www.uchicago.edu/html/groups/theory">
<!WA7><img align=middle
src="http://cs-www.uchicago.edu/images/buttons/text/theory-button.gif" border=0 ALT="Theory"></a>

<hr>
<!-- hhmts start -->
Last modified: Mon Mar 27 11:25:07 1995
<!-- hhmts end -->

<address>millard@cs.uchicago.edu</address>
</BODY>
</HTML>

